package leetcode位运算;

import javax.security.auth.Subject;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IntSummaryStatistics;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.IntStream;

public class A187重复的DNA序列 {

    public static void main(String[] args) {
        String s="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        List<String> repeatedDnaSequences = findRepeatedDnaSequences(s);
        System.out.println(repeatedDnaSequences.size());
    }


    public static List<String> findRepeatedDnaSequences(String s) {
        /**
         * 位运算
         * 用Set<Integer>存储已经已有的数据如果存在就加入到List
         * 设置TACG每个字符用两个bit位表示
         * T 00
         * A 01
         * C 10
         * G 11
         * 十个字符就是20位所以用一个20位的二进制来做窗口
         */
        /**
         * 这里设置字符串数组的长度为128的原因是英文大小写字母总 a:97 z:122 A:65 Z:90
         * 但是这里开辟的是128，因为128是2的7次，用来避免内存碎片整理
         */
        char[] chars=new char[128];
        chars['T']=0;
        chars['A']=1;
        chars['C']=2;
        chars['G']=3;

        int bitmap=0;//用来存储字bit位
        HashSet<Integer> set=new HashSet();
        List<String> list=new ArrayList();

        for (int i = 0; i < s.length(); i++) {
            bitmap<<=2;//两个bit存储下一个字符
            bitmap|=chars[s.charAt(i)];//加上当前字符的bit位

            //最重要的一步制造窗口
            bitmap=bitmap & 0x0000FFFFF;
            if(i >= 9 && set.contains(bitmap)){
                //截取字符
                list.add(s.substring(i-9,i+1));
            }
            set.add(bitmap);
        }
        return list;
    }
}


class Test{
    public static void main(String[] args) {
        System.out.println(Integer.valueOf('a'));
        System.out.println(Integer.valueOf('z'));
        System.out.println(Integer.valueOf('A'));
        System.out.println(Integer.valueOf('Z'));
        System.out.println(128 & (128-1));
        System.out.println(128 >>1);
        int s=3;
        char a=(char)3;
        System.out.println(a);
        System.out.println((int)'0'); //48
        System.out.println((int)'9'); //57
    }


    class Solution {
        List<List<Integer>> allList=new ArrayList();
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            dfs(nums,0,new ArrayList<Integer>());
            return allList;
        }


        public void dfs(int[] nums,int index,List<Integer> list){
            if(index==nums.length-1){
                list.add(nums[index]);
                allList.add(list);
                return;
            }
            list.add(nums[index]);
            allList.add(list);
            List<Integer> tmpList=new ArrayList<Integer>(list);
            dfs(nums,index+1,tmpList);
        }
    }

}